翻訳と辞書
Words near each other
・ Maximum Diner
・ Maximum disjoint set
・ Maximum Downside Exposure (MDE)
・ Maximum Drive
・ Maximum elevation figure
・ Maximum engineering data rate
・ Maximum entropy
・ Maximum entropy probability distribution
・ Maximum entropy spectral estimation
・ Maximum entropy thermodynamics
・ Maximum Experimental Safe Gap
・ Maximum Exposure
・ Maximum Fantastic Four
・ Maximum Fighting Championship
・ Maximum Fighting Championship (2012) events
Maximum flow problem
・ Maximum Force
・ Maximum Fun
・ Maximum Games
・ Maximum Groove
・ Maximum harmonisation
・ Maximum Homerdrive
・ Maximum II
・ Maximum Illud
・ Maximum Integrated Data Acquisition System
・ Maximum intensity projection
・ Maximum intercuspation
・ Maximum Jee&Jee
・ Maximum Joy
・ Maximum Joy (album)


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Maximum flow problem : ウィキペディア英語版
Maximum flow problem

In optimization theory, maximum flow problems involve finding a feasible flow through a single-source, single-sink flow network that is maximum.
The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem.
==History==
The maximum flow problem was first formulated in 1954 by T. E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow.
In 1955, Lester R. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm, the Ford–Fulkerson algorithm.〔Ford, L.R., Jr.; Fulkerson, D.R., ''Flows in Networks'', Princeton University Press (1962).〕
Over the years, various improved solutions to the maximum flow problem were discovered, notably the shortest augmenting path algorithm of Edmonds and Karp and independently Dinitz; the blocking flow algorithm of Dinitz; the push-relabel algorithm of Goldberg and Tarjan; and the binary blocking flow algorithm of Goldberg and Rao. The electrical flow algorithm of Christiano, Kelner, Madry, and Spielman finds an approximately optimal maximum flow but only works in undirected graphs.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Maximum flow problem」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.